// https://leetcode.cn/problems/partition-list/
/*
给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

你应当 保留 两个分区中每个节点的初始相对位置。
*/
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
#include <iostream>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
		// 旧链
		ListNode * dummy = new ListNode(-1);
		ListNode * dummyHead = dummy;
		
		// 新链
		ListNode * dummyNew = new ListNode(-1);
		ListNode * dummyNewHead = dummyNew;
		
		dummy->next = head;
		
		while(dummy->next){
			if(dummy->next->val < x){
				ListNode * tmpNext = dummy->next;
				// 新节点
				dummyNew->next = tmpNext;
				dummyNew = tmpNext;
				
				//旧结点删除
				dummy->next = tmpNext->next; // 这里已经包括指针下移的操作
			}else if(dummy->next){
				// 递增
				dummy = dummy->next;
			}
		}
		dummyNew->next = dummyHead->next;
		return dummyNewHead->next;
    }
	
	// 官方解法 更好
	ListNode* partition1(ListNode* head, int x) {
		ListNode * small = new ListNode(0);
		ListNode * smallHead = small;
		ListNode * big = new ListNode(0);
		ListNode * bigHead = big;
		
		while(head != nullptr){
			if(head->val < x){
				small->next = head;
				small = small->next;
			}else{
				big->next = head;
				big = big->next;
			}
			
			head = head->next;
		}
		big->next = nullptr;
		small->next = bigHead->next;
		return smallHead->next;
	}
	
	ListNode * init(){
		ListNode * head = new ListNode(1);
		ListNode * head1 = new ListNode(4);
		ListNode * head2 = new ListNode(3);
		ListNode * head6 = new ListNode(0);
		ListNode * head7 = new ListNode(0);
		ListNode * head3 = new ListNode(2);
		ListNode * head4 = new ListNode(5);
		ListNode * head5 = new ListNode(2);
		head->next = head1;
		head1->next = head2;
		head2->next = head6;
		head6->next = head7;
		head7->next = head3;
		head3->next = head4;
		head4->next = head5;
		return head;
	}
	
	void show(ListNode * head){
		while(head){
			cout << head->val << ",";
			head = head->next;
		}
		cout << endl;
	}
};

int main(){
	Solution so;
	ListNode * node = so.init();
	so.show(node);
	ListNode * newNode = so.partition1(node, 3);
	so.show(newNode);
	return 0;
}
